package algorithm.recursionAndbacktrack.combination.p39;

import java.util.*;

class Solution {
    private List<List<Integer>> combinations;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        combinations = new ArrayList<>();
        if (candidates != null && candidates.length > 0) {
            combinationSum(candidates,0, target, new ArrayDeque<>());
        }

        return combinations;
    }

    public void combinationSum(int[] candidates, int lastNum, int target, Deque<Integer> combination) {
        if (target <= 0) {
            if(target == 0)
                combinations.add(new ArrayList<>(combination));
            return;
        }

        for (int i = 0; i < candidates.length; i++) {
            if (candidates[i] >= lastNum) {
                combination.addLast(candidates[i]);
                combinationSum(candidates, candidates[i], target - candidates[i], combination);
                combination.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().combinationSum(new int[]{2, 3, 6, 7}, 7));
    }

}